package com.gitee.ywj1352.算法.week01;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 三数之和 {

    //1。 返回不重复的三元组
    //2。 会有复数，无序
    //3。 可能不存在（实际要求返回空数组）
    //4。 a+b+c=0 -> a + b = -c
    //5。 数组内有重复数字， 结果有可能有重复


    // 双指针 两边夹逼
    //
    public static ArrayList<ArrayList<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        for (int i = 1; i < nums.length; i++) {
            int target = -nums[i - 1];
            int left = i;
            int right = nums.length - 1;

            if (nums[i] == nums[i - 1]) continue;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    ArrayList<Integer> integers = new ArrayList<>();
                    integers.add(nums[i - 1]);
                    integers.add(nums[left]);
                    integers.add(nums[right]);
                    res.add(integers);
                    left++;
                }
                if (nums[left] + nums[right] < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }

    public int[] LIS(int[] arr) {
        // write code here
        int[] dp = new int[arr.length];
        int max = 1;
        dp[0] = 1;
        for (int i = 1; i < arr.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            max = Math.max(max, dp[i]);
        }
        return null;
    }


}
